home *** CD-ROM | disk | FTP | other *** search
/ World of Video / World of Video.iso / gfxprograms / 3dprograms / rayshade-4.0 / rayshade / raytrace.c < prev    next >
C/C++ Source or Header  |  1995-02-13  |  12KB  |  497 lines
  1. /*
  2.  * raytrace.c
  3.  *
  4.  * Copyright (C) 1989, 1991, Craig E. Kolb
  5.  * All rights reserved.
  6.  *
  7.  * This software may be freely copied, modified, and redistributed
  8.  * provided that this copyright notice is preserved on all copies.
  9.  *
  10.  * You may not distribute this software, in whole or in part, as part of
  11.  * any commercial product without the express consent of the authors.
  12.  *
  13.  * There is no warranty or other guarantee of fitness of this software
  14.  * for any purpose.  It is provided solely "as is".
  15.  *
  16.  * raytrace.c,v 4.1 1994/08/09 08:07:13 explorer Exp
  17.  *
  18.  * raytrace.c,v
  19.  * Revision 4.1  1994/08/09  08:07:13  explorer
  20.  * Bump version to 4.1
  21.  *
  22.  * Revision 1.1.1.1  1994/08/08  04:52:28  explorer
  23.  * Initial import.  This is a prerelease of 4.0.6enh3, or 4.1 possibly.
  24.  *
  25.  * Revision 4.0.1.1  92/01/10  17:13:02  cek
  26.  * patch3: Made status report print actual scanline number.
  27.  * 
  28.  * Revision 4.0  91/07/17  14:50:49  kolb
  29.  * Initial version.
  30.  * 
  31.  */
  32.  
  33. #include "rayshade.h"
  34. #include "libsurf/atmosphere.h"
  35. #include "libsurf/surface.h"
  36. #include "libcommon/sampling.h"
  37. #include "options.h"
  38. #include "stats.h"
  39. #include "raytrace.h"
  40. #include "viewing.h"
  41.  
  42. #define UNSAMPLED    -1
  43. #define SUPERSAMPLED    -2
  44.  
  45. typedef struct {
  46.     Pixel    *pix;    /* Pixel values */
  47.     int    *samp;    /* Sample number */
  48. } Scanline;
  49.  
  50. static int        *SampleNumbers;
  51. static void    RaytraceInit();
  52.  
  53. static Ray    TopRay;                /* Top-level ray. */
  54. Float        SampleTime();
  55.  
  56. Pixel        WhitePix = {1., 1., 1., 1.},
  57.         BlackPix = {0., 0., 0., 0.};
  58.  
  59. /*
  60.  * "Dither matrices" used to encode the 'number' of a ray that samples a
  61.  * particular portion of a pixel.  Hand-coding is ugly, but...
  62.  */
  63. static int OneSample[1] =     {0};
  64. static int TwoSamples[4] =    {0, 2,
  65.                  3, 1};
  66. static int ThreeSamples[9] =    {0, 2, 7,
  67.                  6, 5, 1,
  68.                  3, 8, 4};
  69. static int FourSamples[16] =    { 0,  8,  2, 10,
  70.                  12,  4, 14,  6,
  71.                   3, 11,  1,  9,
  72.                  15,  7, 13,  5};
  73. static int FiveSamples[25] =    { 0,  8, 23, 17,  2,
  74.                  19, 12,  4, 20, 15,
  75.                   3, 21, 16,  9,  6,
  76.                  14, 10, 24,  1, 13,
  77.                  22,  7, 18, 11,  5};
  78. static int SixSamples[36] =    { 6, 32,  3, 34, 35,  1,
  79.                   7, 11, 27, 28,  8, 30,
  80.                  24, 14, 16, 15, 23, 19,
  81.                  13, 20, 22, 21, 17, 18,
  82.                  25, 29, 10,  9, 26, 12,
  83.                  36,  5, 33,  4,  2, 31};
  84. static int SevenSamples[49] =    {22, 47, 16, 41, 10, 35,  4,
  85.                   5, 23, 48, 17, 42, 11, 29,
  86.                  30,  6, 24, 49, 18, 36, 12,
  87.                  13, 31,  7, 25, 43, 19, 37,
  88.                  38, 14, 32,  1, 26, 44, 20,
  89.                  21, 39,  8, 33,  2, 27, 45,
  90.                  46, 15, 40,  9, 34,  3, 28};
  91. static int EightSamples[64] =    { 8, 58, 59,  5,  4, 62, 63,  1,
  92.                  49, 15, 14, 52, 53, 11, 10, 56,
  93.                  41, 23, 22, 44, 45, 19, 18, 48,
  94.                  32, 34, 35, 29, 28, 38, 39, 25,
  95.                  40, 26, 27, 37, 36, 30, 31, 33,
  96.                  17, 47, 46, 20, 21, 43, 42, 24,
  97.                   9, 55, 54, 12, 13, 51, 50, 16,
  98.                  64,  2,  3, 61, 60,  6,  7, 57};
  99.  
  100. void    AdaptiveRefineScanline(), FullySamplePixel(), FullySampleScanline(),
  101.     SingleSampleScanline();
  102. static int    ExcessiveContrast();
  103. static Scanline scan0, scan1, scan2;
  104.  
  105.  
  106. void
  107. raytrace(argc, argv)
  108. int argc;
  109. char **argv;
  110. {
  111.     int y, *tmpsamp;
  112.     Pixel *tmppix;
  113.     Float usertime, systime, lasttime;
  114.  
  115.     /*
  116.      * If this is the first frame,
  117.      * allocate scanlines, etc.
  118.      */
  119.     if (Options.framenum == Options.startframe)
  120.         RaytraceInit();
  121.     /*
  122.      * The top-level ray TopRay always has as its origin the
  123.      * eye position and as its medium NULL, indicating that it
  124.      * is passing through a medium with index of refraction
  125.      * equal to DefIndex.
  126.      */
  127.     TopRay.pos = Camera.pos;
  128.     TopRay.media = (Medium *)0;
  129.     TopRay.depth = 0;
  130.  
  131.     /*
  132.      * Always fully sample the bottom and top rows and the left
  133.      * and right column of pixels.  This minimizes artifacts that
  134.      * may arise when piecing together images.
  135.      */
  136.     FullySampleScanline(0, &scan0);
  137.  
  138.     SingleSampleScanline(1, &scan1);
  139.     FullySamplePixel(0, 1, &scan1.pix[0], &scan1.samp[0]);
  140.     FullySamplePixel(Screen.xsize -1, 1, &scan1.pix[Screen.xsize -1],
  141.         &scan1.samp[Screen.xsize -1]);
  142.  
  143.     lasttime = 0;
  144.     for (y = 1; y < Screen.ysize; y++) {
  145.         SingleSampleScanline(y+1, &scan2);
  146.         FullySamplePixel(0, y+1, &scan2.pix[0], &scan2.samp[0]);
  147.         FullySamplePixel(Screen.xsize -1, y+1,
  148.             &scan2.pix[Screen.xsize -1],
  149.             &scan2.samp[Screen.xsize -1]);
  150.  
  151.         if (Sampling.sidesamples > 1)
  152.             AdaptiveRefineScanline(y,&scan0,&scan1,&scan2);
  153.  
  154.         PictureWriteLine(scan0.pix);
  155.  
  156.         tmppix = scan0.pix;
  157.         tmpsamp = scan0.samp;
  158.         scan0.pix = scan1.pix;
  159.         scan0.samp = scan1.samp;
  160.         scan1.pix = scan2.pix;
  161.         scan1.samp = scan2.samp;
  162.         scan2.pix = tmppix;
  163.         scan2.samp = tmpsamp;
  164.  
  165.         if ((y+Screen.miny-1) % Options.report_freq == 0) {
  166.             fprintf(Stats.fstats,"Finished line %d (%lu rays",
  167.                         y+Screen.miny-1,
  168.                         Stats.EyeRays);
  169.             if (Options.verbose) {
  170.                 /*
  171.                  * Report total CPU and split times.
  172.                  */
  173.                 RSGetCpuTime(&usertime, &systime);
  174.                 fprintf(Stats.fstats,", %2.2f sec,",
  175.                         usertime+systime);
  176.                 fprintf(Stats.fstats," %2.2f split",
  177.                         usertime+systime-lasttime);
  178.                 lasttime = usertime+systime;
  179.             }
  180.             fprintf(Stats.fstats,")\n");
  181.             (void)fflush(Stats.fstats);
  182.         }
  183.  
  184.     }
  185.     /*
  186.      * Supersample last scanline.
  187.      */
  188.     for (y = 1; y < Screen.xsize -1; y++) {
  189.         if (scan0.samp[y] != SUPERSAMPLED)
  190.             FullySamplePixel(y, Screen.ysize -1,
  191.                 &scan0.pix[y],
  192.                 &scan0.samp[y]);
  193.     }
  194.     PictureWriteLine(scan0.pix);
  195. }
  196.  
  197. void
  198. SingleSampleScanline(line, data)
  199. int line;
  200. Scanline *data;
  201. {
  202.     Float upos, vpos, yp;
  203.     int x, usamp, vsamp;
  204.     Pixel tmp;
  205.  
  206.     yp = line + Screen.miny - 0.5*Sampling.filterwidth;
  207.     for (x = 0; x < Screen.xsize; x++) {
  208.         /*
  209.          * Pick a sample number...
  210.          */
  211.         data->samp[x] = nrand() * Sampling.totsamples;
  212.         /*
  213.          * Take sample corresponding to sample #.
  214.          */
  215.         usamp = data->samp[x] % Sampling.sidesamples;
  216.         vsamp = data->samp[x] / Sampling.sidesamples;
  217.  
  218.         vpos = yp + vsamp * Sampling.filterdelta;
  219.         upos = x + Screen.minx - 0.5*Sampling.filterwidth +
  220.                 usamp*Sampling.filterdelta;
  221.         if (Options.jitter) {
  222.             vpos += nrand()*Sampling.filterdelta;
  223.             upos += nrand()*Sampling.filterdelta;
  224.         }
  225.         TopRay.time = SampleTime(SampleNumbers[data->samp[x]]);
  226.         SampleScreen(upos, vpos, &TopRay,
  227.             &data->pix[x], SampleNumbers[data->samp[x]]);
  228.         if (Options.samplemap)
  229.             data->pix[x].alpha = 0;
  230.     }
  231. }
  232.  
  233. void
  234. FullySampleScanline(line, data)
  235. int line;
  236. Scanline *data;
  237. {
  238.     int x;
  239.  
  240.     for (x = 0; x < Screen.xsize; x++) {
  241.         data->samp[x] = UNSAMPLED;
  242.         FullySamplePixel(x, line, &data->pix[x], &data->samp[x]);
  243.     }
  244. }
  245.  
  246. void
  247. FullySamplePixel(xp, yp, pix, prevsamp)
  248. int xp, yp;
  249. Pixel *pix;
  250. int *prevsamp;
  251. {
  252.     Float upos, vpos, u, v;
  253.     int x, y, sampnum;
  254.     Pixel ctmp;
  255.  
  256. #ifdef AMIGA
  257. #ifdef LATTICE
  258.     chkabort();
  259. #else
  260. #ifndef __GNUC__
  261.     Chk_Abort();
  262. #endif
  263. #endif
  264. #endif
  265.     if (*prevsamp == SUPERSAMPLED)
  266.         return;    /* already done */
  267.  
  268.     Stats.SuperSampled++;
  269.     if (*prevsamp == UNSAMPLED) {
  270.         /*
  271.          * No previous sample; initialize to black.
  272.          */
  273.         pix->r = pix->g = pix->b = pix->alpha = 0.;
  274.     } else {
  275.         if (Sampling.sidesamples == 1) {
  276.             *prevsamp = SUPERSAMPLED;
  277.             return;
  278.         }
  279.         x = *prevsamp % Sampling.sidesamples;
  280.         y = *prevsamp / Sampling.sidesamples;
  281.         pix->r *= Sampling.filter[x][y];
  282.         pix->g *= Sampling.filter[x][y];
  283.         pix->b *= Sampling.filter[x][y];
  284.         pix->alpha *= Sampling.filter[x][y];
  285.     }
  286.  
  287.     sampnum = 0;
  288.     xp += Screen.minx;
  289.     vpos = Screen.miny + yp - 0.5*Sampling.filterwidth;
  290.     for (y = 0; y < Sampling.sidesamples; y++,
  291.          vpos += Sampling.filterdelta) {
  292.         upos = xp - 0.5*Sampling.filterwidth;
  293.         for (x = 0; x < Sampling.sidesamples; x++,
  294.              upos += Sampling.filterdelta) {
  295.             if (sampnum != *prevsamp) {
  296.                 if (Options.jitter) {
  297.                     u = upos + nrand()*Sampling.filterdelta;
  298.                     v = vpos + nrand()*Sampling.filterdelta;
  299.                 } else {
  300.                     u = upos;
  301.                     v = vpos;
  302.                 }
  303.                 TopRay.time = SampleTime(SampleNumbers[sampnum]);
  304.                 SampleScreen(u, v, &TopRay, &ctmp,
  305.                     SampleNumbers[sampnum]);
  306.                 pix->r += ctmp.r*Sampling.filter[x][y];
  307.                 pix->g += ctmp.g*Sampling.filter[x][y];
  308.                 pix->b += ctmp.b*Sampling.filter[x][y];
  309.                 pix->alpha += ctmp.alpha*Sampling.filter[x][y];
  310.             }
  311.             if (++sampnum == Sampling.totsamples)
  312.                 sampnum = 0;
  313.         }
  314.     }
  315.  
  316.     if (Options.samplemap)
  317.         pix->alpha = 255;
  318.  
  319.     *prevsamp = SUPERSAMPLED;
  320. }
  321.  
  322. void
  323. AdaptiveRefineScanline(y, scan0, scan1, scan2)
  324. int y;
  325. Scanline *scan0, *scan1, *scan2;
  326. {
  327.     int x, done;
  328.  
  329.     /*
  330.      * Walk down scan1, looking at 4-neighbors for excessive contrast.
  331.      * If found, supersample *all* neighbors not already supersampled.
  332.      * The process is repeated until either there are no
  333.      * high-contrast regions or all such regions are already supersampled.
  334.      */
  335.  
  336.     do {
  337.         done = TRUE;
  338.         for (x = 1; x < Screen.xsize -1; x++) {
  339.             /*
  340.               * Find min and max RGB for area we care about
  341.              */
  342.             if (ExcessiveContrast(x, scan0->pix, scan1->pix,
  343.                 scan2->pix)) {
  344.                 if (scan1->samp[x-1] != SUPERSAMPLED) {
  345.                     done = FALSE;
  346.                     FullySamplePixel(x-1, y,
  347.                         &scan1->pix[x-1],
  348.                         &scan1->samp[x-1]);
  349.                 }
  350.                 if (scan0->samp[x] != SUPERSAMPLED) {
  351.                     done = FALSE;
  352.                     FullySamplePixel(x, y-1,
  353.                         &scan0->pix[x],
  354.                         &scan0->samp[x]);
  355.                 }
  356.                 if (scan1->samp[x+1] != SUPERSAMPLED) {
  357.                     done = FALSE;
  358.                     FullySamplePixel(x+1, y,
  359.                         &scan1->pix[x+1],
  360.                         &scan1->samp[x+1]);
  361.                 }
  362.                 if (scan2->samp[x] != SUPERSAMPLED) {
  363.                     done = FALSE;
  364.                     FullySamplePixel(x, y+1,
  365.                         &scan2->pix[x],
  366.                         &scan2->samp[x]);
  367.                 }
  368.                 if (scan1->samp[x] != SUPERSAMPLED) {
  369.                     done = FALSE;
  370.                     FullySamplePixel(x, y,
  371.                         &scan1->pix[x],
  372.                         &scan1->samp[x]);
  373.                 }
  374.             }
  375.         }
  376.     } while (!done);
  377. }
  378.  
  379. static int
  380. ExcessiveContrast(x, pix0, pix1, pix2)
  381. int x;
  382. Pixel *pix0, *pix1, *pix2;
  383. {
  384.     Float mini, maxi, sum, diff;
  385.  
  386.     maxi = max(pix0[x].r, pix1[x-1].r);
  387.     if (pix1[x].r > maxi) maxi = pix1[x].r;
  388.     if (pix1[x+1].r > maxi) maxi = pix1[x+1].r;
  389.     if (pix2[x].r > maxi) maxi = pix2[x].r;
  390.  
  391.     mini = min(pix0[x].r, pix1[x-1].r);
  392.     if (pix1[x].r < mini) mini = pix1[x].r;
  393.     if (pix1[x+1].r < mini) mini = pix1[x+1].r;
  394.     if (pix2[x].r < mini) mini = pix2[x].r;
  395.  
  396.     diff = maxi - mini;
  397.     sum = maxi + mini;
  398.     if (sum > EPSILON && diff/sum > Options.contrast.r)
  399.         return TRUE;
  400.  
  401.     maxi = max(pix0[x].g, pix1[x-1].g);
  402.     if (pix1[x].g > maxi) maxi = pix1[x].g;
  403.     if (pix1[x+1].g > maxi) maxi = pix1[x+1].g;
  404.     if (pix2[x].g > maxi) maxi = pix2[x].g;
  405.  
  406.     mini = min(pix0[x].g, pix1[x-1].g);
  407.     if (pix1[x].g < mini) mini = pix1[x].g;
  408.     if (pix1[x+1].g < mini) mini = pix1[x+1].g;
  409.     if (pix2[x].g < mini) mini = pix2[x].g;
  410.  
  411.     diff = maxi - mini;
  412.     sum = maxi + mini;
  413.  
  414.     if (sum > EPSILON && diff/sum > Options.contrast.g)
  415.         return TRUE;
  416.  
  417.     maxi = max(pix0[x].b, pix1[x-1].b);
  418.     if (pix1[x].b > maxi) maxi = pix1[x].b;
  419.     if (pix1[x+1].b > maxi) maxi = pix1[x+1].b;
  420.     if (pix2[x].b > maxi) maxi = pix2[x].b;
  421.  
  422.     mini = min(pix0[x].b, pix1[x-1].b);
  423.     if (pix1[x].b < mini) mini = pix1[x].b;
  424.     if (pix1[x+1].b < mini) mini = pix1[x+1].b;
  425.     if (pix2[x].b < mini) mini = pix2[x].b;
  426.  
  427.     diff = maxi - mini;
  428.     sum = maxi + mini;
  429.     if (sum > EPSILON && diff/sum > Options.contrast.b)
  430.         return TRUE;
  431.  
  432.     return FALSE;
  433. }
  434.  
  435. Float
  436. SampleTime(sampnum)
  437. int sampnum;
  438. {
  439.     Float window, jitter = 0.0, res;
  440.  
  441.     if (Options.shutterspeed <= 0.)
  442.         return Options.framestart;
  443.     if (Options.jitter)
  444.         jitter = nrand();
  445.     window = Options.shutterspeed / Sampling.totsamples;
  446.     res = Options.framestart + window * (sampnum + jitter);
  447.     TimeSet(res);
  448.     return res;
  449. }
  450.  
  451. static void
  452. RaytraceInit()
  453. {
  454.  
  455.     switch (Sampling.sidesamples) {
  456.         case 1:
  457.             SampleNumbers = OneSample;
  458.             break;
  459.         case 2:
  460.             SampleNumbers = TwoSamples;
  461.             break;
  462.         case 3:
  463.             SampleNumbers = ThreeSamples;
  464.             break;
  465.         case 4:
  466.             SampleNumbers = FourSamples;
  467.             break;
  468.         case 5:
  469.             SampleNumbers = FiveSamples;
  470.             break;
  471.         case 6:
  472.             SampleNumbers = SixSamples;
  473.             break;
  474.         case 7:
  475.             SampleNumbers = SevenSamples;
  476.             break;
  477.         case 8:
  478.             SampleNumbers = EightSamples;
  479.             break;
  480.         default:
  481.             RLerror(RL_PANIC,
  482.                 "Sorry, %d rays/pixel not supported.\n",
  483.                     Sampling.totsamples);
  484.     }
  485.  
  486.     /*
  487.       * Allocate pixel arrays and arrays to store sampling info.
  488.       */
  489.     scan0.pix = (Pixel *)Malloc(Screen.xsize * sizeof(Pixel));
  490.     scan1.pix = (Pixel *)Malloc(Screen.xsize * sizeof(Pixel));
  491.     scan2.pix = (Pixel *)Malloc(Screen.xsize * sizeof(Pixel));
  492.  
  493.     scan0.samp = (int *)Malloc(Screen.xsize * sizeof(int));
  494.     scan1.samp = (int *)Malloc(Screen.xsize * sizeof(int));
  495.     scan2.samp = (int *)Malloc(Screen.xsize * sizeof(int));
  496. }
  497.